package com.zzz.dynamic.triangle;

public class TriangleMaxSum {
    public static void main(String[] args) {
        int[][] triangle = new int[4][];
        triangle[0] = new int[]{1};
        triangle[1] = new int[]{2, 3};
        triangle[2] = new int[]{4, 5, 6};
        triangle[3] = new int[]{7, 8, 9, 10};

        System.out.println(getMaxSum(triangle));
    }

    public static int getMaxSum(int[][] triangle) {

        int temp[][] = new int[triangle.length][triangle.length];

        // return deal(0, 0, 0, 0, triangle);
        // return deal2(0, 0, triangle, temp);

        return deal3(triangle);
    }

    // 自顶向下求解，
    // 该方法同样重复计算了，把步骤列一下
    // 1+2
    // 1+2+4
    // 1+2+4+7
    // 1+2+4+8
    // 1+2+5
    // 1+2+5+8
    // 1+2+5+9
    // 1+3
    // 1+3+5
    // 1+3+5+8
    // 1+3+5+9
    // 1+3+6+9
    // 1+3+6+10
    // 从上面步骤来看 5节点后面相加的计算重复了两遍
    // 5+8
    // 5+9
    // 这就是隐藏的重复步骤，完全可以省略掉一次计算     而因为不是非常的直观所以就感觉没有重复计算
    public static int deal(int i, int j, int lastValue, int sum, int[][] triangle) {

        System.out.println("访问节点 " + j + " " + i);

        sum = Math.max(lastValue + triangle[j][i], sum);
        //System.out.println("计算" + lastValue + " + " + triangle[j][i] + " = " + sum);

        if (j == triangle.length - 1) {
            return sum;
        }

        int sum1 = deal(i, j + 1, lastValue + triangle[j][i], sum, triangle);
        int sum2 = deal(i + 1, j + 1, lastValue + triangle[j][i], sum, triangle);
        sum = Math.max(sum1, sum2);
        return sum;
    }

    // 自底向上求解
    // 这种吧单个节点作为最大值来看待就很直观的知道哪里重复了
    // 计算 2 和 3 的最大值时，都要计算max(5)这个节点，而一眼就能看到5这个节点计算被重复了
    public static int deal2(int i, int j, int[][] triangle, int[][] temp) {
        //System.out.println("访问节点 " + triangle[j][i]);
        if (j == triangle.length - 1) {
            return triangle[j][i];
        }

        // 如果缓存数组中对应的坐标存放了最大值，那么就取
        int leftMax = temp[j + 1][i] == 0 ? deal2(i, j + 1, triangle, temp) + triangle[j][i] : temp[j + 1][i] + triangle[j][i];
        System.out.println("计算" + triangle[j][i] + " = " + leftMax + " 左");

        int rightMax = temp[j + 1][i + 1] == 0 ? deal2(i + 1, j + 1, triangle, temp) + triangle[j][i] : temp[j + 1][i + 1] + triangle[j][i];
        System.out.println("计算" + triangle[j][i] + " = " + rightMax + " 右");

        // 计算得到的最大值放入缓存数组对应的坐标位置中，以便后续使用
        temp[j][i] = Math.max(leftMax, rightMax);
        System.out.println("计算" + triangle[j][i] + " 最大值 " + temp[j][i]);

        return Math.max(leftMax, rightMax);
    }

    // 使用遍历方法而不适用递归，尽量避免栈溢出  使用递推方式，只需要遍历每层数组即可
    public static int deal3(int[][] triangle) {
        int[][] temp = new int[triangle.length][triangle.length];

        for (int i = triangle.length - 1; i >= 0; i--) {
            for (int j = 0; j <= triangle[i].length - 1; j++) {
                if (i == triangle.length - 1) {
                    temp[i][j] = triangle[i][j];
                } else {
                    temp[i][j] = triangle[i][j] + Math.max(temp[i][j + 1], temp[i + 1][j + 1]);
                }
            }
        }
        return temp[0][0];
    }

    // 接续优化，我们发现临时数据空间有很大的浪费，从使用情况来看，临时数组只需要一层即可，完全不需要二维
    public static int deal4(int[][] triangle) {
        int[] temp = new int[triangle.length];
        for (int i = triangle.length - 1; i >= 0; i--) {
            for (int j = 0; j <= triangle[i].length - 1; j++) {
                if (i == triangle.length - 1) {
                    temp[j] = triangle[i][j];
                } else {
                    temp[j] = triangle[j][i] + Math.max(temp[j + 1], temp[j + 1]);
                }
            }
        }
        return temp[0];
    }
}
